/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
 
 // step 1# 定义队列结构（用于层序遍历）
 typedef struct {
     struct TreeNode** data;  // 存储指针的数组
     int front;               // 队首指针
     int rear;                // 队尾指针
     int capacity;            // 队列容量
 } Queue;
 
 // step 2# 创建队列
 Queue* createQueue(int capacity) {
     Queue* queue = (Queue*)malloc(sizeof(Queue));
     queue->data = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * capacity);
     queue->front = 0;
     queue->rear = 0;
     queue->capacity = capacity;
     return queue;
 }
 
 // step 3# 判断队列是否为空
 bool isEmpty(Queue* queue) {
     return queue->front == queue->rear;
 }
 
 // step 4# 入队
 void enqueue(Queue* queue, struct TreeNode* node) {
     if ((queue->rear + 1) % queue->capacity != queue->front) {
         queue->data[queue->rear++] = node;
     }
 }
 
 // step 5# 出队
 struct TreeNode* dequeue(Queue* queue) {
     if (!isEmpty(queue)) {
         return queue->data[queue->front++];
     }
     return NULL;
 }
 
 // step 6# 队列大小
 int queueSize(Queue* queue) {
     return queue->rear - queue->front;
 }
 
 // step 7# 释放队列
 void freeQueue(Queue* queue) {
     free(queue->data);
     free(queue);
 }
 
 // step 8# 主函数：层序遍历
 int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
     int** result = (int**)malloc(sizeof(int*) * 2000);         // 最多2000层
     *returnColumnSizes = (int*)malloc(sizeof(int) * 2000);     // 每层元素个数
     *returnSize = 0;
 
     if (root == NULL) return result;
 
     Queue* queue = createQueue(2000);                          // 创建队列
     enqueue(queue, root);                                      // 根节点入队
 
     // step 8.1# 遍历整棵树
     while (!isEmpty(queue)) {
         int size = queueSize(queue);                           // 当前层的节点数量
         int* level = (int*)malloc(sizeof(int) * size);         // 存储当前层的节点值
 
         // step 8.2# 遍历当前层
         for (int i = 0; i < size; i++) {
             struct TreeNode* node = dequeue(queue);            // 出队一个节点
             level[i] = node->val;                              // 记录该节点的值
 
             if (node->left) enqueue(queue, node->left);        // 左子节点入队
             if (node->right) enqueue(queue, node->right);      // 右子节点入队
         }
 
         result[*returnSize] = level;                           // 记录该层结果
         (*returnColumnSizes)[*returnSize] = size;              // 记录该层大小
         (*returnSize)++;                                       // 层数加一
     }
 
     freeQueue(queue);                                          // 释放队列内存
     return result;
 }
 
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


 // step 1# 递归函数：按层填充节点值
 void dfs(struct TreeNode* cur, int depth, int** result, int* returnSize, int** returnColumnSizes) {
     if (cur == NULL) return;
 
     // step 1.1# 如果当前深度还没有初始化，先分配该层空间
     if (*returnSize == depth) {
         result[depth] = (int*)malloc(sizeof(int) * 1000);  // 假设每层最多1000个节点
         (*returnColumnSizes)[depth] = 0;                  // 初始化当前层节点数量
         (*returnSize)++;                                  // 层数加一
     }
 
     // step 1.2# 将当前节点值加入对应层数组
     result[depth][(*returnColumnSizes)[depth]++] = cur->val;
 
     // step 1.3# 递归处理左子树和右子树，深度 +1
     dfs(cur->left, depth + 1, result, returnSize, returnColumnSizes);
     dfs(cur->right, depth + 1, result, returnSize, returnColumnSizes);
 }
 
 // step 2# 主函数：层序遍历入口
 int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
     int** result = (int**)malloc(sizeof(int*) * 2000);         // 最多支持2000层
     *returnColumnSizes = (int*)malloc(sizeof(int) * 2000);     // 每层节点数
     *returnSize = 0;
 
     dfs(root, 0, result, returnSize, returnColumnSizes);       // 从深度0开始递归填充
     return result;
 }
 